package com.zlk.algorithm.bit.xor;

import org.junit.Test;

/**
 * @program: algorithm
 * @ClassName EvenTimesOddTimes
 * @description:arr中，只有一种数，出现奇数次   arr中，有两种数，出现奇数次
 * @author: slfang
 * @create: 2023-12-22 11:24
 * @Version 1.0
 **/
public class EvenTimesOddTimes {

    @Test
    public void test(){
        int a = 5;
        int b = 7;

        a = a ^ b;
        b = a ^ b;
        a = a ^ b;


        int[] arr1 = { 3, 3, 2, 3, 1, 1, 1, 3, 1, 1, 1 };
        System.out.println(findOneOddNumInArr(arr1));
        int[] arr2 = { 4, 3, 4, 2, 2, 2, 4, 1, 1, 1, 3, 3, 1, 1, 1, 4, 2, 2 };
        findTowOddNumInArr(arr2);

    }

    /**
     * 一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到这一个
     * @param arr
     */
    public int  findOneOddNumInArr(int[] arr){
        int i = 0;
        for (int i1 = 0; i1 < arr.length; i1++) {
            i ^=arr[i1];
        }
        return i;
    }


    /**
     * 一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到这两个数
     * @param arr
     */
    public void findTowOddNumInArr(int[] arr){
        int temp = 0;
        for (int i = 0; i < arr.length; i++) {
            temp = temp^arr[i];
        }
        //此时temp  = a^b   a b 就是这两个奇数
        //由于a b 不等 所以 temp 32位中肯定存在一个位置是等于1 的 ，因为如果a=b a^b=0
        int rightOne = temp & (-temp); // 提取出最右的1;d
        int existOne = 0;
        for (int i = 0; i < arr.length; i++) {
            if((arr[i]&rightOne)!=0){
                existOne^=arr[i];
            }
        }
        System.out.println("奇数1："+existOne);
        System.out.println("奇数2："+(existOne^temp));
    }



}
